package array.sortsColor;
/**
 * @Date 2020/04/08
 * @author 王光浩
 * @Thinking 使用排序方法
 */
public class MyMethodTwo {
	/*
	 * 使用 冒泡排序法，时间复杂度O（n^2），空间复杂度O（1）
	 */
	public void sortColors1(int[] nums) {
		for(int i=0;i<nums.length-1;i++) {
			for(int j=0;j<nums.length-i-1;j++) {
				if(nums[j]>nums[j+1]) {
					nums[j]=nums[j+1]^nums[j];
					nums[j+1]=nums[j+1]^nums[j];
					nums[j]=nums[j+1]^nums[j];
				}
			}
		}
	}
	/*
	 * 使用 选择排序法，时间复杂度O（n^2），空间复杂度O（1）
	 */
	public void sortColors2(int[] nums) {
		for(int i=0;i<nums.length-1;i++) {
			for(int j=i+1;j<nums.length;j++) {
				if(nums[j]<nums[i]) {
					nums[i]=nums[i]^nums[j];
					nums[j]=nums[i]^nums[j];
					nums[i]=nums[i]^nums[j];
				}
			}
		}
	}
	/*
	 * 使用 插入排序法，时间复杂度O（n^2），空间复杂度O（1）
	 */
	public void sortColors3(int[] nums) {
		for(int i=1;i<nums.length;i++) {
			int j=i;
			int tem=nums[i];
			while(j>0 && nums[j-1]>tem) {
				nums[j]=nums[j-1];
				j--;
			}
			nums[j]=tem;
		}
	}
	/*
	 * 使用 快速排序法，时间复杂度O（nlogn），空间复杂度O（n）
	 */
	public void sortColors4(int[] nums) {
		helper(0,nums.length-1,nums);
	}
	private void helper(int left,int right,int[] nums) {
		if(left>=right)return;
		int l=left;
		int r=right;
		int basic=nums[left];
		while(l<r) {
			while(l<r && nums[r]>=basic)r--;
			nums[l]=nums[r];
			while(l<r && nums[l]<=basic)l++;
			nums[r]=nums[l];
		}
		nums[l]=basic;
		helper(left,l,nums);
		helper(l+1,right,nums);
	}
	/*
	 * 使用 并归排序法，时间复杂度O（nlogn），空间复杂度O（n）
	 */
	public void sortColors5(int[] nums) {
		helper1(0,nums.length-1,nums);
	}
	private void helper1(int left,int right,int[] nums) {
		if(left>=right)return;
		int mid=(left+right)/2;
		//分别对两边进行排序（并）
		helper(left,mid,nums);     
		helper(mid+1,right,nums);
		//将两个排序之后的数组进行合并（归）
		int[] tem=new int[right-left+1];
		int l=left;
		int r=right;
		int index=0;
		while(l<=mid && r<=right)tem[index++]=(nums[l]<nums[r])?(nums[l++]):(nums[r++]);
		while(l<=mid)tem[index++]=nums[l++];
		while(r<=right)tem[index++]=nums[r++];
		for(int i=0;i<tem.length;i++) {
			nums[left++]=tem[i];
		}
	}
}
